package com.jxb.four;

import com.jxb.tree.TreeNode;

/**
 * 二叉树的最近公共祖先
 *
 * 思路：
 *  公共祖先只有三种
 *     1：p和q在node的子树中，且分别为node的异侧
 *     2：p为node节点，q为node的左子树或者右子树
 *     3：q为node节点，p为node的左子树或者右子树
 *  实现核心思路点***：有p和q的节点，返回的是p或者q，否则返回的null
 *
 * @author jiaobo
 * @date Created in 2025/1/1 20:58
 **/
public class LowestCommonAncestor_236 {

    //root left right return
    // 0
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        //0
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if (left != null && right != null) {
            return root;
        }
        return left != null ? left : right;
    }

}
